package zw_401_500.zw_414_第三大的数;

import java.util.Arrays;
import java.util.TreeSet;

class Solution {

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 5, 2, 1};
        int thirdMax = thirdMax(nums);
        System.out.println(thirdMax);
    }


    /**
     * 方法一：排序
     * 时间复杂度：O(nlogn)，其中 nn 是数组 nums 的长度。排序需要 O(nlogn) 的时间。
     * 空间复杂度：O(logn)。排序需要的栈空间为 O(logn)。
     *
     * @param nums
     * @return
     */
//    public static int thirdMax(int[] nums) {
//        Arrays.sort(nums);
//        int count = 1;
//        if (nums.length < 3) return nums[nums.length - 1];
//        for (int i = nums.length - 1; i >= 1; i--) {
//            if (nums[i] != nums[i - 1] && ++count == 3) return nums[i - 1];
//        }
//        if (count < 3) return nums[nums.length - 1];
//        return nums[0];
//    }

    /**
     * 方法二：有序集合
     * 时间复杂度：O(n)，其中n是数组nums的长度。由于有序集合的大小至多为3，插入和删除的时间复杂度可以视作是O(1)的，因此时间复杂度为O(n)。
     * 空间复杂度：O(1)。
     *
     * @param nums
     * @return
     */
//    public int thirdMax(int[] nums) {
//        TreeSet<Integer> s = new TreeSet<Integer>();
//        for (int num : nums) {
//            s.add(num);
//            if (s.size() > 3) {
//                s.remove(s.first());
//            }
//        }
//        return s.size() == 3 ? s.first() : s.last();
//    }


    /**
     * 方法三：一次遍历
     * 以遍历数组，并用三个变量 a、b 和 c 来维护数组中的最大值、次大值和第三大值，以模拟方法二中的插入和删除操作。
     *
     * @param nums
     * @return
     */
    public static int thirdMax(int[] nums) {
        Integer a = null, b = null, c = null;
        for (int num : nums) {
            if (a == null || num > a) {
                c = b;
                b = a;
                a = num;
            } else if (a > num && (b == null || num > b)) {
                c = b;
                b = num;
            } else if (b != null && b > num && (c == null || num > c)) {
                c = num;
            }
        }
        return c == null ? a : c;
    }
}
